// 题目要求：
// 给定一个数组 height，表示柱子高度
// 计算柱子中间的凹槽能接多少雨水

// 解题思路：
// 对于 i 位置的柱子，左边最高的柱子的高度用 left[i] 表示
// 右边最高的柱子的高度用 right[i] 表示
// 理由：左右两边都有比 i 位置柱子高的柱子，才能接到雨水
// 细节：
// 求左右位置最高柱子的高度，要考虑上 i 位置的柱子的高度
// 否则，当 i 位置的柱子特别高，就会出现负数
// 求左右位置的柱子的高度可以考虑用动态规划的方式

public class ReceiveRainwater {
    public int trap(int[] height) {
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];

        left[0] = height[0];
        right[n - 1] = height[n - 1];

        for(int i = 1; i < n; i++){
            left[i] = Math.max(left[i - 1], height[i]);
        }

        for(int i = n - 2; i >= 0; i--){
            right[i] = Math.max(right[i + 1], height[i]);
        }

        int ret = 0;
        for(int i = 0; i < n; i++){
            ret += Math.min(left[i], right[i]) - height[i];
        }

        return ret;
    }
}
